#ifndef __LIS_H__
#define __LIS_H__
#include <vector>
#include <unordered_set>
using namespace std;
/*
* leetcode 491 递增子序列
* 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2
*/

/*
* 这里需要注意几个点:
*	1.不能出现重复的组合, 所以需要去重
*	2.去重前不能进行排序, 否则结果不对
* 
* 例如: {4, 7, 6, 7}
* 树形结构:
*							4767
*		4-767			7-67			6-7		7-(x)
* 47-67	46-7 47-(x)  76-7(x) 77(x)		67
* ...
* 如上如树层结构:
*	1.关于去重, 47- 节点, 在同层中取了元素 7, 所以不能再取相同元素
*	2.关于递增, 76-7 节点, 6 < 7, 所以不能选取
* 
* 关于结果的收集, 实际上最终还是去收集子集, 只是需要进行递增判断
* 
* 关于去重, 实际上还是类似于 组合总和 III 的树层去重
*	只是在实现上需要进行调整, 不能对集合进行排序
*/

void BackTrackingLIS(const vector<int>& set, vector<int>& path, vector<vector<int>>& results, int startIndex = 0) {
	if (path.size() >= 2)
		results.push_back(path);

	if (startIndex == set.size())
		return;

	//使用 hash 集合来记录选取的元素, 用于去重判断
	/*
	* 这里可以很明显的看出来:
	*	树层去重其实就是为 单层 记录重复元素, 然后去重
	*/
	unordered_set<int> hashSet;
	for (int i = startIndex; i < set.size(); i++) {
		/*
		* 1.元素是否大于路径的最后一个元素 (是否递增)
		* 2.元素是否在同层选取 (树层去重)
		*/
		if ((!path.empty() && set[i] < path.back()) || 
			hashSet.find(set[i]) != hashSet.end())
			continue;

		hashSet.insert(set[i]);
		path.push_back(set[i]);

		BackTrackingLIS(set, path, results, i + 1);

		//hashSet.erase()	不需要删除元素
		path.pop_back();
	}
}
#endif // __LIS_H__

